Theo thần thoại Hy Lạp, Tiên Nữ Andromeda là con gái của Tiên Vương Cepheus (vua xứ Ethiopia) và Tiên Hậu Cassiopeia (hoàng hậu xứ này). Nàng bị vua cha dâng cho thủy quái đang tàn phá đất nước để cứu xứ sở này và bị thủy quái xích lại. Cuối cùng nàng được Anh Tiên cứu thoát.

Nếu các ngôi sao mờ hơn, nhưng vẫn nhìn được bằng mắt thường trong chòm sao này được tính đến thì chòm sao này trông có dạng như một người que giới nữ, với vành đai nổi bật (giống như chòm sao Lạp Hộ, hay Orion), và trong tay có một cái gì đó có dạng dài gắn vào, tạo ra hình ảnh của một nữ chiến binh cầm kiếm. Chòm sao này cùng với các chòm sao khác trong hoàng đạo như Bạch Dương, một phần của Song Ngư và Pleiades, có thể là nguyên bản của thần thoại về đai lưng của Hippolyte, là một phần trong Mười hai kỳ công của Hercules.

Ngoài ra, bằng cách thêm cả những ngôi sao mờ, mà mắt thường có thể nhìn thấy, thì hình ảnh cũng có thể tưởng tượng như là một thiếu nữ bị giam giữ bởi dây xích, và Andromeda trông có vẻ như đang muốn thoát ra. Cùng với các chòm sao khác bên cạnh (Tiên Vương, Anh Tiên, Tiên Hậu, và có thể là cả Phi Mã, và chòm sao Kình Ngư phía dưới Andromeda, có thể là nguồn gốc của thần thoại về Sự khoe khoang của Cassiopeia, mà nó được nhận ra cùng với thần thoại này.